/**
 * Impute ratings using "similarity-based data smoothing," inspired by
 * Popescul, R., Ungar, L. H., Pennock, D. M., and Lawrence, S. (2001).
 * Probabilistic models for unified collaborative and content-based recommendation in
 * sparse-data environments.
 *
 * For each user we generate ratings to bring its total number of ratings up to
 * min_ratings. To do this, we look at the movies that this user has really
 * rated, and for each one we find similar movies and use those ratings,
 * scaling by the similarity. The details are:
 * 1. We may have so few real ratings that we need to look at several similar 
 *    movies for each one. In this case, we choose the most similar movie, 
 *    then the second most similar movie, etc.
 * 2. The same movie may be similar to several of the movies that the user 
 *    actually rated. To deal with this, we use the arithmetic mean of the
 *    similarity-weighted ratings.
 * 3. The user may have actually rated a movie that is one of the most similar
 *    movies for another movie that the user actually rated. In this case, the
 *    user's real rating stands (we do not smooth it).
 *
 * The inputs are assumed to be rating residuals, so this program does not
 * perform any centering etc. when it averages.
 *
 * Usage:
 * ... num_movies similarity_file min_ratings <training_set
 *
 * num_movies: dimension of similarity matrix (positive)
 * similarity_file: num_movies by num_movies symmetric matrix in binary
 *                  (float) format.
 * min_ratings: augment ratings until all movies have at least this number of
 *              ratings (positive)
 * training_set: sorted by user, in format for ratings_by_user_block_cursor_t
 *
 * Output:
 * user_id:
 * movie_id,residual
 * movie_id,residual
 * ...
 */
#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include "u1.h"
#include "symmetric_matrix.h"
#include "io.h"

using namespace std;

// Indirect less than comparison for a row of a similarity matrix. The most
// similar movies end up at the end of the list.
struct F_similarity_to_less {
  const symmetric_matrix<float> &S;
  int movie_id;
  F_similarity_to_less(const symmetric_matrix<float> &S, int movie_id)
    : S(S), movie_id(movie_id) { }
  bool operator()(int i, int j) const {
    return S(movie_id-1, i) < S(movie_id-1, j);
  }
};

int main(int argc, char **argv) {
  if (argc != 4) {
    TRACE<<"see comments for usage"<<endl;
    exit(EXIT_FAILURE);
  }

  int num_movies_int = atoi(argv[1]);
  if (num_movies_int < 1) {
    TRACE<<"invalid num_movies = "<<num_movies_int<<endl;
    exit(EXIT_FAILURE);
  }
  size_t num_movies = (size_t)num_movies_int;
  string similarity_file = argv[2];
  int min_ratings_int = atoi(argv[3]); 
  if (min_ratings_int < 1) {
    TRACE<<"invalid min_ratings = "<<min_ratings_int<<endl;
    exit(EXIT_FAILURE);
  }
  size_t min_ratings = (size_t)min_ratings_int;

  // Read movie-movie similarity matrix from binary file into memory.
  TRACE<<"loading similarities from "<<similarity_file<<endl;
  symmetric_matrix<float> S(num_movies);
  ifstream S_is(similarity_file.c_str());
  S.read_binary(S_is);
  S_is.close();

  // We will need permutation vectors later.
  vector<vector<int> > pi;
  
  // Store ratings; we need to keep these sorted by user. We want the
  // similarity-weighted average; keep the weighted ratings sum and the number
  // of ratings for each user id.
  typedef map<int, pair<float, int> > ratings_t;
  ratings_t ratings;

  // Process training set from disk (no need to load into memory).
  typedef ratings_by_user_block_cursor_t<float> ts_t;
  ts_t ts(cin);
  for(; ts; ++ts) {
    cout<<ts.user_id()<<":\n";
    if (ts.size() >= min_ratings) {
      // This user has enough ratings already; just print.
      for (ts_t::const_iterator it = ts.begin(); it != ts.end(); ++it)
        cout<<it->id<<','<<it->rating<<'\n';
    } else {
      // This user needs more ratings.
      TRACE<<"smoothing "<<ts.user_id()<<" with "<<ts.size()<<" ratings"<<endl;

      // Put the real ratings into a map for easy reference; we just want to
      // keep them and count them. We won't smooth them. Mark them as having
      // a negative number of entries (we check this later).
      ratings.clear();
      for (ts_t::const_iterator it = ts.begin(); it != ts.end(); ++it)
        ratings.insert(make_pair(it->id, make_pair(it->rating, -1)));

      // Find most similar movies for each movie that the user has rated.
      // The most similar movies are at the end. If there is no similarity 
      // data for a movie, its pi vector is empty.
      for (size_t i = 0; i < ts.size(); ++i) {
        if (i >= pi.size()) {
          pi.push_back(vector<int>(num_movies));
        } 
        if (no_data_for(ts.movie_id(i), S)) {
          TRACE<<"clearing"<<i<<" "<<ts.movie_id(i)<<endl;
          pi[i].clear();
        } else {
          pi[i].resize(num_movies);
          for (size_t j = 0; j < num_movies; ++j) pi[i][j] = j; // iota
          sort(pi[i].begin(), pi[i].end(),
            F_similarity_to_less(S, ts.movie_id(i)));
        }
      }

      int movie_count = 0;
      int j_msm = num_movies-1; // index of most similar movie being considered
      while (ratings.size() < min_ratings && j_msm >= 0) {
        ++movie_count;
        
        for (size_t i = 0; i < ts.size(); ++i) {
          if (pi[i].empty()) continue; // no data

          // Choose movie that is j_msm'th most similar to the movie for
          // this user's i'th rating.
          int movie_id = pi[i][j_msm] + 1;

          // There may be no data for the most similar movie.
          if (no_data_for(movie_id, S)) continue;

          ratings_t::iterator rit = ratings.find(movie_id);
          if (rit == ratings.end())
            rit = ratings.insert(
              make_pair(movie_id, make_pair(0.0f, 0))).first;

          if (rit->second.second != -1) { // don't smooth real ratings
            // Generate the rating from its similarity to the movie for this
            // user's i'th rating.
            float sim = S(ts.movie_id(i)-1, movie_id-1);
            rit->second.first += sim*(ts.rating(i));
            rit->second.second += 1;
          }
        }
        --j_msm;
      }

      // Now average the ratings.
      TRACE<<"now at "<<ratings.size()
        <<" ratings with "<<movie_count<<" movies"<<endl;

      // Now print combined ratings; we must keep them in order by user id,
      // which the map does nicely.
      for (ratings_t::const_iterator rit = ratings.begin();
        rit != ratings.end(); ++rit)
      {
        if (rit->second.second == -1) {
          // A real rating; no smoothing.
          cout<<rit->first<<','<<rit->second.first<<'\n';
        } else {
          cout<<rit->first<<','<<(rit->second.first / rit->second.second)<<'\n';
        }
      }
    }
  }

  TRACE<<"done"<<endl;

  return 0;
}

/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

